package basic.courseLearn09.problem;


import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

//字符串全排列问题
public class StringFullPermutation {

    List<String> results = new ArrayList<>();


    /**
     * 字符串全排列问题，确定第i层的字符（未去重）
     * @param str 字符串
     * @param i 层数
     * @param fixStr 已固定字符
     */
    public void solution_1(String str,int i,String fixStr){
        // 1.递归终止条件
        if(i == str.length()){
            results.add(fixStr);
            return;
        }
        // 2.遍历当前层的字符
        for (int j = i; j < str.length(); j++) {
            // 2.1 交换i和j位置的字符
            str = swap(str,i,j);
            // 2.2 更新已经固定的字符
            String newFixStr = fixStr + str.charAt(i);
            // 2.3 递归
            solution_1(str,i+1,newFixStr);
            // 2.4 恢复字符串
            str = swap(str,i,j);

        }
    }

    /**
     * 字符串全排列问题，确定第i层的字符（去重）
     * @param str 字符串
     * @param i 层数
     * @param fixStr 已固定字符
     */
    public void solution_2(String str,int i,String fixStr){
        // 1.递归终止条件
        if(i == str.length()){
            results.add(fixStr);
            return;
        }
        // 2.遍历当前层的字符
        boolean[] visited = new boolean[26];
        for (int j = i; j < str.length(); j++) {
            if (visited[str.charAt(j)-'a']) continue;
            visited[str.charAt(j)-'a'] = true;
            // 2.1 交换i和j位置的字符
            str = swap(str,i,j);
            // 2.2 更新已经固定的字符
            String newFixStr = fixStr + str.charAt(i);
            // 2.3 递归
            solution_2(str,i+1,newFixStr);
            // 2.4 恢复字符串
            str = swap(str,i,j);

        }
    }

    private String swap(String str, int i, int j) {
        if(i == j) return str;
        char temp_1 = str.charAt(i);
        char temp_2 = str.charAt(j);
        str = str.substring(0,i) + temp_2 + str.substring(i+1,j) + temp_1 + str.substring(j+1);
        return str;
    }

    @Test
    public void test_solution_1(){
        String str = "abc";
        solution_2(str,0,"");
        results.forEach(System.out::println);
    }


}
